// https://www.lintcode.com/problem/remove-dights/

public class Solution {
    /**
     * @param num: a number
     * @param k: the k digits
     * @return: the smallest number
     */
    public String removeKdigits(String num, int k) {
        // write your code here.
        StringBuilder ret = new StringBuilder();
        int new_len = num.length() - k;
        if (k <= 0) {
            return num;
        } else if (k >= num.length()) {
            return "0";
        } else {
            for (int i = 0; i < num.length(); ++i) {
                while ((ret.length() > 0) && (k > 0) && (ret.charAt(ret.length() - 1) > num.charAt(i))) {
                    // 当前元素比栈顶元素小，且还有数字可以删除。
                    ret.deleteCharAt(ret.length() - 1);
                    --k;
                }
                ret.append(num.charAt(i));
            }
        }
        int start = 0;
        while ((start < new_len) && (ret.charAt(start) == '0')) {
            ++ start;
        }
        if (start >= new_len) {
            return "0";
        }
        return ret.substring(start, new_len).toString();
    }
}